package com.zxy.allSearcher;

import java.util.*;

/**
 * @author zxy
 * @since 2023/9/14
 **/
public class Demo {
    public static void main(String[] args) {
    }

    public static int maxArea(int[] height) {
        int l = 0;
        int r = height.length - 1;
        int max = 0;
        while (l < r) {
            if (height[l] < height[r]) {
                max = Math.max(max, height[l] * (r - l));
                l++;
            } else {
                max = Math.max(max, height[r] * (r - l));
                r--;
            }
        }
        System.out.println(max);
        return max;
    }

    // 横向/纵向，在字符串长度差异较大的情况下，性能最优
    public static String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        if (strs.length == 1) {
            return strs[0];
        }
        // 默认第一个字符为公共前缀，为公共前缀长
        int preLen = strs[0].length();
        int count = strs.length;
        char cur;
        // 纵向比较字符，
        for (int i = 0; i < preLen; i++) {
            cur = strs[0].charAt(i);
            for (int j = 1; j < count; j++) {
                // 可能比较突兀，这样理解：纵向比较，i==长度最小的字符串==最大的公共前缀
                // 每当匹配时i++，当i==str时，代表已经匹配到长度最小且正好是最大的公共前缀（没有后续比其更小了，是否可以提前退出？）
                if (i == strs[j].length() || strs[j].charAt(i) != cur) {
                    return strs[0].substring(0, i);
                }
            }
        }
        // 当长度为1时，出现的情况
        return strs[0];
    }

    public static List<List<Integer>> threeSum(int[] nums) {
        int len = nums.length;
        // 数据如果无序，对后续数据的筛选不便，而且无序的数据，无疑会加重数据的复杂性
        Arrays.sort(nums);
        List<List<Integer>> tem = new ArrayList<>();

        int third;
        int tar;
        for (int first = 0; first < len; first++) {
            // 相邻元素必须不相等，否则会出现重复
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }

            // 二/三重循环并列执行（因为有规律）
            // c一定在b的右边，从大到小排，效率更高
            third = len - 1;
            // 但我自己又发现的一条规律，因为排好了序，1、一旦a为正，后续的b，c也一定为正，2,、一旦c为负，a，b一定为负，差异是我们的朋友
            if (nums[first] > 0 || nums[third] < 0) {
                // 原来是没有打印
                System.out.println(tem);
                return tem;
            }
            // 正负影响不大，最后比较的是是否与 b+c相等
            tar = -nums[first];

            for (int second = first + 1; second < len; second++) {
                // b必须在a元素之后，且不重复
                if (second > first + 1 && nums[second] == nums[second - 1]) {
                    continue;
                }
                // 只获取数和为0
                while (second < third && nums[second] + nums[third] > tar) {
                    --third;
                }
                // 双指针交叉
                if (second == third) {
                    break;
                }
                if (nums[second] + nums[third] == tar) {
                    tem.add(Arrays.asList(nums[first], nums[second], nums[third]));
                }
            }
        }
        System.out.println(tem);
        return tem;
    }

    public int threeSumClosest(int[] nums, int target) {
        int len = nums.length;
        int max = target;

        int third;
        int tar;
        for (int first = 0; first < len; first++) {
            third = len - 1;
            tar = -nums[first];

            for (int second = first + 1; second < len; second++) {
                // 只获取数和为0
                while (second < third) {

                    --third;
                }
                // 双指针交叉
                if (second == third) {
                    break;
                }

                if (nums[second] + nums[third] == tar) {
                    // tem.add(Arrays.asList(nums[first], nums[second], nums[third]));
                }
            }
        }
        return 0;
    }

    public int minSubArrayLen(int target, int[] nums) {
        int result = Integer.MAX_VALUE;
        int sum = 0;
        int sumLen = 0;
        for (int i = 0; i < nums.length; i++) {
            sum = 0;
            for (int j = i; j < nums.length; j++) {
                sum += nums[j];
                if (sum >= target) {
                    sumLen = j - i + 1; // 子序列的长度
                    result = result < sumLen ? result : sumLen;
                    break;
                }
            }
        }
        return result == Integer.MAX_VALUE ? 0 : result;
    }

    public int totalFruit(int[] fruits) {
        int len = fruits.length;
        if (len < 3) {
            return len;
        }

        int ans = 0;
        int classCnt = 0;
        int left = 0, right = 0; // 序列边界
        Map<Integer, Integer> classMap = new HashMap<>();

        while (right < len) {
            if (classMap.get(fruits[right]) == null) {
                classCnt++;
            }
            classMap.put(fruits[right], 1);
            while (classCnt > 2) {
                if (classMap.get(fruits[left]) == 1) {
                    classCnt--;
                }
                left++;
            }
            ans = Math.max(ans, right - left + 1);
            right++;
        }
        return ans;
    }
}
